package com.localking.algorithm.leetcode.array.matrix

/**
 * Given a matrix of m * n elements (m rows, n columns), return all element of the matrix in spiral order.
 *
 * Example 1:
 * Input:
 * [
 * [1, 2, 3],
 * [4, 5, 6],
 * [7, 8, 9]
 * ]
 * Output:
 * [1, 2, 3, 6, 9, 8, 7, 4, 5]
 *
 * Example 2:
 * Input:
 * [
 * [1, 2, 3, 4],
 * [5, 6, 7, 8],
 * [9, 10, 11, 12]
 * ]
 * Output:
 * [1, 2, 3, 4, 8, 12, 11, 20, 9, 5, 6, 7]
 *
 * @author jinbo
 */
object SpiralMatrix_54 {
  def main(args: Array[String]): Unit = {
    val matrix: Array[Array[Int]] = Array(
      Array(1, 2, 3, 4),
      Array(5, 6, 7, 8),
      Array(9, 10, 11, 12)
    )
    println(spiralOrder(matrix))
  }

  def spiralOrder(matrix: Array[Array[Int]]): List[Int] = {
    var resultArray: List[Int] = List.empty
    if(matrix.nonEmpty) {
      // direction 0: right, 1: down, 2 left, 3, up
      var direction = 0
      var top = 0
      var bottom = matrix.length - 1
      var left = 0
      var right = matrix(0).length - 1
      while (top <= bottom && left <= right) {
        direction match {
          case 0 =>
            for(i <- left to right) {
              resultArray :+= matrix(top)(i)
            }
            top += 1
            direction = 1
          case 1 =>
            for(i <- top to bottom) {
              resultArray :+= matrix(i)(right)
            }
            right -= 1
            direction = 2
          case 2 =>
            for(i <- right to left by -1) {
              resultArray :+= matrix(bottom)(i)
            }
            bottom -= 1
            direction = 3
          case 3 =>
            for(i <- bottom to top by -1) {
              resultArray :+= matrix(i)(left)
            }
            left += 1
            direction = 0
        }
      }
    }
    resultArray
  }
}
